package leetcode;

public class MyLinkList implements IList{
    //内部类
    class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val=val;
        }
    }
    //创建一个链表
    public Node head;
    public void create(){
        Node node1=new Node(12);
        Node node2=new Node(13);
        Node node3=new Node(14);
        node1.next=node2;
        node2.next=node3;
        head=node1;
    }
    @Override
    public void addFirst(int data) {
    Node node=new Node(data);
    node.next=head;
    head=node;
    }

    @Override
    public void addLast(int data) {
    Node node=new Node(data);
    Node last=head;
    while (last.next!=null){
        last=last.next;
    }
    last.next=node;
    }

    @Override
    public void addIndex(int index, int data) {
        if(index<0||index>size()){
            System.out.println("位置不合法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        Node curNode=head;
        while (index-1>0){
            curNode=curNode.next;
            index--;
        }
        Node node=new Node(data);
        Node nextnode=curNode.next;
        curNode.next=node;
        node.next=nextnode;
    }
    public Node getNode(int index){
        Node node=head;
        while (index>0){
            node=node.next;
            index--;
        }
        return node;
    }
    @Override
    public boolean contains(int key) {
        Node node=new Node(key);
        while (node!=null){
            if(node.val==key){
                return true;
            }
            node=node.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        Node pre=head;
        Node cur=head;
        if(head.val==key){
            head=head.next;
            return;
        }
        while (cur!=null){
            if(cur.val==key){
                Node nextnode=pre.next;
                pre.next=cur;
                cur.next=nextnode;
            }else {
                pre=cur;
                cur=cur.next;
            }
        }
    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        Node node=head;
        int n=0;
        while (node!=null){
            node=node.next;
            n++;
        }
        return n;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {
        Node node=head;
        while (node!=null){
            System.out.print(node.val+" ");
            node=node.next;
        }
    }
    //反转链表
    public Node reverseList(){
        if(head==null||head.next==null){
            return head;
        }
        Node cur=head.next;
        head.next=null;
        while (cur!=null){
            Node nextNode=cur.next;
            cur.next=head;
            head=cur;
            cur=nextNode;
        }
        return head;
    }
    //返回中间结点
    public Node middleNode(){
        Node fast=head;
        Node slow=head;
        while (fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //返回倒数第k个结点
    public Node findK(int k){
        Node fast=head;
        Node slow=head;
        if(k<=0||head==null){
            return null;
        }
        while (k-1>0){
            fast=fast.next;
            k--;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return  slow;
    }
    //合并两个升序链表
    public Node mergeTwoList(Node list1,Node list2){
        Node phead=new Node(-1);
        Node node=phead;
        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                node.next=list1;
                list1=list1.next;
            }else {
                node.next=list2;
                list2=list2.next;
            }
            node=node.next;
        }
        if(list1!=null){
            node.next=list1;
        }
        if(list2!=null){
            node.next=list2;
        }
        return phead.next;
    }
    //链表分割
    public Node portition(int x){
        Node as=null;
        Node ae=null;
        Node bs=null;
        Node be=null;
        Node node=head;
        while (node!=null){
            if(node.val<x){
                if(as==null){
                    as=node;
                    ae=node;
                    node=node.next;
                }else {
                    ae.next=node;
                    node=node.next;
                    ae=ae.next;
                }
            }else {
                if(bs==null){
                    bs=node;
                    be=node;
                    node=node.next;
                }else {
                    be.next=node;
                    node=node.next;
                    be=be.next;
                }
            }
        }
        if(as==null){
            return bs;
        }
        ae.next=bs;
        if(bs!=null){
            be.next=null;
        }
        head=as;
        return head;
    }
    //是否回文
    public boolean palin(){
        if(head==null||head.next==null){
            return true;
        }
        Node mid=middleNode();
        //翻转
        Node ehead=mid;
        Node cur=ehead.next;
        while (cur!=null){
           Node nodeNext= cur.next;
           cur.next=ehead;
           ehead=cur;
           cur=nodeNext;
        }
        Node snode=head;
        Node enode=ehead;
        while (snode!=enode){
            if(snode.val!=enode.val){
                return false;
            }
            if(snode.next==enode){
                return true;
            }
            snode=snode.next;
            ehead=enode.next;
        }
        return true;
    }
    //相交链表
    public Node getIntersectionNode(Node headA, Node headB) {
        int A=size(headA);
        int B=size(headB);
        if(A>B){
            int l=A-B;
            while (l>0&&headA!=null){
                headA=headA.next;
                l--;
            }
        }else {
            int l=B-A;
            while (l>0&&headB!=null){
                headB=headB.next;
                l--;
            }
        }
        while (headA!=null){
            if(headA==headB){
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }
    public int size(Node head){
        int n=0;
        Node node=head;
        while(node!=null){
            node=node.next;
            n++;
        }
        return n;
    }
    //是否为环形链表
    public Node hasCycle(Node head) {
        Node fast=head;
        Node slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return fast;
            }
        }
        return null;
    }
    //判断入环结点
    public Node detectCycle(Node head) {
        Node fast=hasCycle(head);
        if(fast==null){
            return null;
        }
        Node slow=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }

    public static void main(String[] args) {
        MyLinkList myLinkList=new MyLinkList();
        myLinkList.create();
        Node node=myLinkList.getNode(2);
        myLinkList.addIndex(1,39);
        myLinkList.addIndex(2,22);
        myLinkList.addIndex(0,16);
        myLinkList.display();
        System.out.println();
        myLinkList.reverseList();
        myLinkList.display();
        System.out.println();
        myLinkList.portition(13);
        myLinkList.display();

    }
}
